package com.linyaonan.leetcode.medium._199;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,2,3,null,5,null,4]
 * 输出: [1, 3, 4]
 * 解释:
 * <p>
 * 1            <---
 * /   \
 * 2     3         <---
 * \     \
 * 5     4       <---
 *
 * @author: Lin
 * @date: 2020/1/19
 */
public class BinaryTreeRightSideView {
    Map<Integer, Integer> map;
    int maxSize = 0;
    ArrayList<Integer> result;


    public List<Integer> rightSideView(TreeNode root) {
        map = new HashMap<>();
        dfs(root, 0);
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= maxSize; i++) {
            result.add(map.get(i));
        }
        return result;
    }

    private void dfs(TreeNode node, int index) {
        if (node != null) {
            dfs(node.left, ++index);
            map.put(index, node.val);
            maxSize = Math.max(maxSize, index);
            index--;
            dfs(node.right, ++index);
        }
    }

    /**
     * 层序遍历，记录最后一个元素即可
     * @param root
     * @return
     */
    public List<Integer> rightSideView2(TreeNode root) {
        result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        bfs(root);
        return result;
    }

    private void bfs(TreeNode node) {
        ArrayList<TreeNode> cur = new ArrayList<>();
        cur.add(node);
        while (!cur.isEmpty()) {
            ArrayList<TreeNode> next = new ArrayList<>();
            ArrayList<Integer> tmp = new ArrayList<>();
            for (TreeNode c : cur) {
                tmp.add(c.val);
                if (c.left != null) {
                    next.add(c.left);
                }
                if (c.right != null) {
                    next.add(c.right);
                }
            }
            result.add(tmp.get(tmp.size() - 1));
            cur = next;
        }

    }

    /**
     * 二叉树的右视图，就是层序遍历取到一层的最后一个数值
     * @param root
     * @return
     */
    public List<Integer> rightSideView3(TreeNode root) {
        // 1. 异常边界
        if (root == null) {
            return new ArrayList<>();
        }

        LinkedList<TreeNode> treeNodes = new LinkedList<>();
        treeNodes.add(root);

        List<Integer> result = new ArrayList<>();

        while (!treeNodes.isEmpty()) {
            LinkedList<TreeNode> temp = new LinkedList<>();
            Integer last = null;
            for (TreeNode treeNode : treeNodes) {
                if (treeNode.left != null) {
                    temp.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    temp.add(treeNode.right);
                }
                last = treeNode.val;
            }
            result.add(last);
            treeNodes = temp;
        }

        return result;
    }
}
